package com.zhledu.datastructure.gragh;

import lombok.extern.slf4j.Slf4j;

import java.io.Serializable;
import java.util.*;

@Slf4j
public class MyADGragh {
    private final static int MAX_INT = Integer.MAX_VALUE;

    private class AdjNode {
        public Serializable name;
        public int index;
        public int weight;
        public AdjNode next;

        public AdjNode(Serializable name, int index, int weight) {
            this.name = name;
            this.index = index;
            this.weight = weight;
            this.next = null;
        }

        public AdjNode(Serializable name, int index) {
            this.name = name;
            this.index = index;
            this.next = null;
        }
    }


    private class ALGragh {
        public List<AdjNode> vex = new ArrayList();
        public int vexnum, edgenum;
    }

    List<Boolean> visited = new ArrayList<>();

    private ALGragh g = new ALGragh();

    public void initGragh() {
        Scanner scanner = new Scanner(System.in);
        System.out.println("请输入顶点数和边数（空格隔开）");
        g.vexnum = scanner.nextInt();
        g.edgenum = scanner.nextInt();

        System.out.println("请依次输入" + g.vexnum + "个顶点信息");
        for (int i = 0; i < g.vexnum; i++) {
            g.vex.add(new AdjNode(scanner.next(), i));
        }

        System.out.println("请依次输入边的值，和该条边上的权值，以空格隔开：");
        while (g.edgenum-- > 0) {
            Serializable u = scanner.next();
            Serializable v = scanner.next();
            int w = scanner.nextInt();
            AdjNode start = locateVex(u);
            AdjNode end = locateVex(v);
            if (start != null && end != null) {
                insertEdge(start, end, w);
            }
        }
    }

    public void testInitGragh() {
        g.vexnum = 5;
        g.edgenum = 8;
        String[] vs = "a,b,c,d,e".split(",");
        for (int i = 0; i < vs.length; i++) {
            g.vex.add(i, new AdjNode(vs[i], i));
        }
        String es = "a b 5:" +
                "a c 4:" +
                "b c 3:" +
                "a e 8:" +
                "c e 7:" +
                "c d 4:" +
                "d e 2";
        String[] vss = es.split(":");
        for (int n = 0; n < vss.length; n++) {
            Scanner scanner = new Scanner(vss[n]);
            Serializable u = scanner.next();
            Serializable v = scanner.next();
            int w = scanner.nextInt();
            AdjNode start = locateVex(u);
            AdjNode end = locateVex(v);
            if (start != null && end != null) {
                insertEdge(start, end, w);
            }
        }


    }

    private AdjNode locateVex(Serializable u) {
        for (int i = 0; i < g.vexnum; i++) {
            if (g.vex.get(i).name.equals(u)) {
                return g.vex.get(i);
            }
        }
        return null;
    }

    public void insertEdge(AdjNode start, AdjNode end, int w) {
        AdjNode insert = new AdjNode(end.name, end.index);
        insert.weight = w;
        insert.next = start.next;
        start.next = insert;
    }

    public void print() {
        System.out.println("打印顶点信息");
        for (int i = 0; i < g.vexnum; i++) {
            System.out.print(i + ":" + g.vex.get(i).name + " ");
            AdjNode node = g.vex.get(i).next;
            while (node != null) {
                System.out.print("->" + node.name + "(" + node.weight + ")");
                node = node.next;
            }
            System.out.println();
        }
        System.out.println();
    }

    public void bfs(Serializable start) {
        List<AdjNode> vex = new ArrayList<>();
        Queue<AdjNode> queue = new ArrayDeque();
        AdjNode index = locateVex(start);
        visited.add(index.index, true);
        vex.add(index);
        queue.offer(index);
        while (!queue.isEmpty()) {
            index = queue.poll();
            while (index != null) {
                if (!visited.get(index.index)) {
                    visited.set(index.index, true);
                    queue.offer(g.vex.get(index.index));
                    vex.add(index);
                }
                index = index.next;
            }
        }
        System.out.println("使用广度优先算法得到的点为：");
        for (AdjNode point : vex) {
            System.out.print(point.name + "\t");
        }
        System.out.println();

    }

    public void dfs(Serializable start) {
        AdjNode index = locateVex(start);
        visited.set(index.index, true);
        System.out.print(index.name + "\t");
        index = index.next;
        while (index != null) {
            if (!visited.get(index.index)) {
                dfs(index.name);
            }
            index = index.next;
        }
    }

    public void emptyVisited(){
        visited=new ArrayList<>();
        for(int i=0;i<g.vexnum;i++)
        {
            visited.add(false);
        }
    }


    public static void main(String[] args) {
        MyADGragh gragh = new MyADGragh();
        gragh.testInitGragh();
        gragh.print();
        gragh.emptyVisited();
        gragh.bfs("a");
        System.out.println("使用深度优先算法得到的顶点：");
        gragh.emptyVisited();
        gragh.dfs("a");
    }


}
